home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 289_01 / buildlvl.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-05-23  |  13.4 KB  |  431 lines
  1. /*-----------------------------------------------------------------------------
  2. Build the tree of moves down to a given level.
  3.  
  4. Revision History
  5. ----------------
  6. NAME            DATE            MODS
  7. Gary Culp       19 Dec 1988 -
  8.                  2 Jan 1988     Initial version
  9. -----------------------------------------------------------------------------*/
  10. #include <stdio.h>
  11. #include "othello.h"
  12.  
  13. STATIC int after_opponents_move(move_type humans_move);
  14.  
  15. STATIC void build_children_of_a_board(
  16.    key_type parent_limb_key,
  17.    key_type parent_board_key,
  18.    unsigned char movers_color);
  19.  
  20. STATIC int build_a_level(void);
  21.  
  22. /* return values from build_a_level() */
  23. #define BT_COMPLETED  0
  24. #define BT_DBFULL     1
  25.  
  26. /*
  27.    This level:
  28.  
  29.    board/limb  has children?  is bottom?
  30.    -------------------------------------
  31.   -limb----------n--------------n------------ERROR
  32.   -limb----------n------------y--------------ERROR
  33.    limb        y                n         descend along each child
  34.    limb        y              y           return
  35.    board         n              n         build children
  36.    board         n            y           return
  37.   -board-------y----------------n------------ERROR
  38.    board       y              y           return
  39. */
  40.  
  41.  
  42. /*
  43. Keep track of the depth to which the tree has been fully built.
  44. */
  45. STATIC int tree_depth = 0;
  46.  
  47. /*
  48. The build_tree function is iterative rather than recursive because building the
  49. tree is asynchronous to the human's move; and we want to take advantage of
  50. information about the human's move immediately (by pruning moves he didn't
  51. make from the tree).
  52.  
  53. Information for manually-recursive tree build:
  54.    'stack' of limb keys
  55.    desired depth (actually use value of stack index at desired depth; which
  56.       turns out to be the desired depth - 2)
  57.    stack pointer for stack of limb keys (actually an index rather than
  58.       a pointer)
  59.    mover's color at current depth
  60. */
  61. STATIC key_type limb_key_stack[BT_MAX_DEPTH];
  62. STATIC int bt_desired_nest;
  63. STATIC int bt_current_nest; /* "stack pointer" (index) for limb_key_stack */
  64. STATIC unsigned char bt_movers_color;
  65.  
  66. STATIC int human_state;
  67. /* defines for human_state */
  68. #define HS_NOT_HUMANS_TURN    0
  69. #define HS_WAITING_FOR_HUMAN  1
  70. #define HS_HUMAN_MOVED        2
  71.  
  72. STATIC humans_move_limb_key;
  73.  
  74.  
  75. /*
  76. Build the tree to the specified level
  77.  
  78. The function builds the tree until it reaches the specified depth, or
  79. the database fills up.
  80.  
  81. If movers_color == THEM_PIECE:
  82.    The function will also check for input from the human player while it is
  83.    building the tree.  If it has to stop building the tree, it will continue
  84.    to check for the human's input.  It will not return until the human player
  85.    has input his move.
  86. If movers_color == US_PIECE:
  87.    The function will not check for input from the human player.
  88.  
  89. This function assumes that the root of the tree corresponds to the current
  90. state of the board.
  91.  
  92. Returns:
  93.    depth to which tree was completely built
  94. */
  95. int
  96. build_tree(int depth_to_build, unsigned char movers_color)
  97. {
  98.    struct limb_struct far *limb_ptr;
  99.    int temp;
  100.  
  101.    if (movers_color == THEM_PIECE) {
  102.       human_state = HS_WAITING_FOR_HUMAN;
  103.       depth_to_build++; /* We'll delete 1 level after the human moves; so we
  104.                            build an extra level now. */
  105.    }
  106.    else {
  107.       human_state = HS_NOT_HUMANS_TURN;
  108.    }
  109.  
  110.    limb_ptr = db_retrieve_limb(curnt_top_limb);
  111.    if (limb_ptr->move & BOARD_MASK) {
  112.       /* The root is a board.  There is a lower-level function
  113.          (after_opponents_move()) which assumes that the root is not a board,
  114.          so we have to build the first level of the tree before continuing.
  115.       */
  116.       build_children_of_a_board(curnt_top_limb,
  117.                                 limb_ptr->bc.board_key,
  118.                                 movers_color);
  119.       tree_depth = 1;
  120.    }
  121.  
  122.    for (bt_desired_nest = tree_depth - 1;
  123.         bt_desired_nest <= depth_to_build - 2;
  124.         bt_desired_nest++)
  125.    {
  126.       limb_key_stack[0] = limb_ptr->bc.child_key;
  127.       bt_current_nest = 0;
  128.       bt_movers_color = movers_color ^ (US_PIECE | THEM_PIECE);
  129.  
  130.       /* Try to build a level. If the database fills up but we're waiting for
  131.          input from the human, keep trying to build until we get his input.
  132.       */
  133.       do {
  134.          temp = build_a_level();
  135.       } while (temp != BT_COMPLETED && human_state == HS_WAITING_FOR_HUMAN);
  136.  
  137.       if (temp == BT_COMPLETED) {
  138.          tree_depth = bt_desired_nest + 2;
  139.       }
  140.       else {
  141.          break;
  142.       }
  143.    }
  144.  
  145.    /* We may finish building the tree to the depth we desire before the
  146.       human opponent enters his move.  If this happens, this loop will wait
  147.       for him to enter his move.
  148.    */
  149.    while (human_state == HS_WAITING_FOR_HUMAN) {
  150.       move_type humans_move;
  151.  
  152.       if ((humans_move = check_for_input()) != HASNT_MOVED) {
  153.          human_state = HS_HUMAN_MOVED;
  154.          after_opponents_move(humans_move);
  155.       }
  156.    }
  157.  
  158.    if (movers_color == THEM_PIECE) {
  159.  
  160.       free_limb(curnt_top_limb);   /* delete root limb */
  161.  
  162.       /* Make limb for human's move the new root limb */
  163.       curnt_top_limb = humans_move_limb_key;
  164.  
  165.       tree_depth--;  /* Since we deleted the old root, the tree is shallower */
  166.    }
  167.    return (tree_depth);
  168. }
  169.  
  170.  
  171. /*
  172. Build another level onto the tree
  173. This function communicates through static variables.
  174.  
  175. Returns:
  176.    BT_COMPLETED: finished building the level
  177.    BT_DBFULL:    had to stop building because database was almost full
  178. */
  179. STATIC int
  180. build_a_level()
  181. {
  182.    limb_type far *limb_ptr;
  183.    move_type humans_move;
  184.  
  185.    while (1) {       /* exit from loop by 'return's */
  186.       if (human_state == HS_WAITING_FOR_HUMAN  &&
  187.           (humans_move = check_for_input()) != HASNT_MOVED)
  188.       {
  189.          human_state = HS_HUMAN_MOVED;
  190.          if (after_opponents_move(humans_move)) {
  191.             return (BT_COMPLETED);
  192.          }
  193.       }
  194.  
  195.       /*
  196.       If the database is almost full, stop building.
  197.       Resume build at this point later on, after the tree has been trimmed.
  198.       */
  199.       if (db_almost_full()) {
  200.          return (BT_DBFULL);
  201.       }
  202.  
  203.       /* Limbs have either a board or children.
  204.          If this limb has a board, build its children now.
  205.       */
  206.  
  207.       limb_ptr = db_retrieve_limb(limb_key_stack[bt_current_nest]);
  208.  
  209.       if (limb_ptr->move & BOARD_MASK) {  /* it's a board */ 
  210.          build_children_of_a_board(limb_key_stack[bt_current_nest],
  211.                                  limb_ptr->bc.board_key,
  212.                                  bt_movers_color);
  213.       }
  214.  
  215.       /*
  216.          Figure out next limb key to examine (leave on top of limb_key_stack)
  217.       */
  218.       if (bt_current_nest != bt_desired_nest) {
  219.          /* Follow child key to nest down one level */
  220.          limb_key_stack[bt_current_nest + 1] =
  221.             db_retrieve_limb(limb_key_stack[bt_current_nest])->bc.child_key;
  222.          ++bt_current_nest;
  223.          bt_movers_color ^= (US_PIECE | THEM_PIECE);
  224.       }
  225.       else {
  226.          while (bt_current_nest >= 0) {   /* also contains a 'break' */
  227.             /* 
  228.                Replace limb key on top of stack with its next sibling;
  229.                if it has no next sibling, pop it off the stack.
  230.             */
  231.             if (
  232.                 (limb_key_stack[bt_current_nest] =
  233.                  db_retrieve_limb(limb_key_stack[bt_current_nest])->sibling_key
  234.                 )
  235.                 == NO_KEY
  236.                )
  237.             {
  238.                --bt_current_nest;  /* pop stack */
  239.                bt_movers_color ^= (US_PIECE | THEM_PIECE);
  240.             }
  241.             else {
  242.                break; /* exit from loop */
  243.             }
  244.          }
  245.  
  246.          if (bt_current_nest < 0) {
  247.             /* a complete level of the tree has been built */
  248.             return (BT_COMPLETED);
  249.          }
  250.       }
  251.    }
  252. }
  253.  
  254.  
  255. /*
  256. Build all the child boards for a given parent_limb.
  257. The parent_limb must have a board (not child limbs) associated with it.
  258. */
  259. STATIC void
  260. build_children_of_a_board(
  261.    key_type parent_limb_key,
  262.    key_type parent_board_key,
  263.    unsigned char movers_color)
  264. {
  265.    struct board_struct parent_board;
  266.    struct board_struct child_board;
  267.    int aff_list[MAX_AFFECTED_PIECES];  /* list of pieces affected by move */
  268.    int aff_ct;        /* number of pieces affected by move (incl. new piece) */
  269.    int look_at;       /* begin search for move at this offset within .board */
  270.    move_type db_move; /* move, encoded the way database functions want it */
  271.  
  272.    if (db_retrieve_board(parent_board_key, &parent_board)) {
  273.       /* This should NEVER happen. If it does, there's a bug in the program. */
  274.       printf("\nFATAL PROGRAM BUG:\n\
  275. couldn't retrieve parent board in build_children_of_a_board\n");
  276.       exit(5);
  277.    }
  278.  
  279.    /* init vars */
  280.    look_at = 0;   /* start at beggining of board */
  281.  
  282.    while (aff_ct = find_move(&parent_board, look_at, movers_color, aff_list)) {
  283.       /* Let child inherit info from parent, then make changes. */
  284.  
  285.       child_board = parent_board;
  286.  
  287.       update_protection_for_board(&child_board, aff_list, aff_ct,
  288.          movers_color);
  289.  
  290.       db_move = 0;
  291.       SET_ROW_COL(db_move, aff_list[0] / 10 - 1, aff_list[0] % 10 - 1);
  292.  
  293.       if (db_add_child(parent_limb_key, db_move, &child_board,
  294.                        bd_eval(&child_board, US_PIECE)     ) == -1)
  295.       {
  296.          /* This shouldn't be possible -- we check for room in the database 
  297.             earlier
  298.          */
  299.          printf("OTHELLO FATAL: no room to add board to database\n");
  300.          exit(5);
  301.       }
  302.  
  303.       look_at = aff_list[0] + 1; /* resume search for moves at next cell */
  304.    }
  305.  
  306.    /* If there are NO moves at all for this player, we still have to add
  307.       a child board (with a special move code) to the database.
  308.    */
  309.    if (look_at == 0) {
  310.  
  311.       /* look_at == 0 iff there are NO moves were found */
  312.  
  313.       /* With the board scoring scheme in effect 3Jan1989, the score for
  314.          this board will the same as the parent board's score.
  315.          In most cases, there will be moves available.  Therefore, this
  316.          code will rarely be executed.  Therefore, the performance gain
  317.          from short-cutting the evaluation of these boards is slight.
  318.          For this reason, I chose to fully evaluate the board.
  319.       */
  320.  
  321.       if (db_add_child(parent_limb_key, NO_MOVE_MASK, &parent_board,
  322.                        bd_eval(&parent_board, US_PIECE)     ) == -1)
  323.       {
  324.          /* This shouldn't be possible -- we check for room in the database 
  325.             earlier
  326.          */
  327.          printf("OTHELLO FATAL: no room to add board to database\n");
  328.          exit(5);
  329.       }
  330.    }
  331. }
  332.  
  333.  
  334. /*
  335. This function should be called after the opponent has entered his move.
  336. It clears out unneeded parts of the database and, if necessary, adjusts
  337. the variables for the tree build.
  338.  
  339. This function assumes that there are limbs for the children of the root.
  340. (In other words, the tree has been built to at least one level below the root.)
  341.  
  342. Returns:
  343.    A flag indicating whether the current build phase for the subtree 
  344.    corresponding to the human's move has been completed.
  345.       0: not completed
  346.       1: completed
  347. */
  348. STATIC int
  349. after_opponents_move(move_type humans_move)
  350. {
  351.    key_type key;
  352.    struct limb_struct far *limb_ptr;
  353.    int already_built;
  354.    int ret_val;
  355.  
  356.    already_built = 1;
  357.  
  358.    /* for each limb below root of tree */
  359.    for (key = db_retrieve_limb(curnt_top_limb)->bc.child_key;
  360.         key != NO_KEY;
  361.         key = limb_ptr->sibling_key)
  362.    {
  363.  
  364.       /* Retrieve the limb */
  365.       limb_ptr = db_retrieve_limb(key);
  366.  
  367.       /* if this is the limb at the top of the subtree currently being built */
  368.       if (key == limb_key_stack[0]) {
  369.          /* This and subsequent parts of the tree haven't been fully built to
  370.             the desired depth.
  371.          */
  372.          already_built = 0;
  373.       }
  374.  
  375.       /* if this limb corresponds to the human's move */
  376.       if ((limb_ptr->move & ~BOARD_MASK) == humans_move) {
  377.          /* Remember whether this subtree has been completed. */
  378.          ret_val = already_built;
  379.  
  380.          /* Remember the limb key for the human's move. */
  381.          humans_move_limb_key = key;
  382.  
  383.          /* If this is not the limb at the top of the subtree currently
  384.             being built, reset the limb 'stack' to start over at this limb.
  385.          */
  386.          if (key != limb_key_stack[0]) {
  387.             bt_current_nest = 0;
  388.             limb_key_stack[0] = key;
  389.             bt_movers_color = US_PIECE;
  390.          }
  391.       }
  392.       else {
  393.          /* delete this limb & its subtree */
  394.          db_delete_subtree(curnt_top_limb, key);
  395.       }
  396.    }
  397.  
  398.    return (ret_val);
  399. }
  400.  
  401.  
  402. /*
  403. This function is to be called after we (the computer) move.
  404. It deletes all our possible moves except the one we made, deletes the old
  405. root of the tree, and sets the new root to be the move we just made.
  406.  
  407. The tree_depth variable is also updated to reflect these changes.
  408. */
  409. void
  410. update_tree_after_our_move(
  411.    key_type our_move)
  412. {
  413.    register key_type ch;
  414.    limb_type far *l;
  415.  
  416.    ch = db_retrieve_limb(curnt_top_limb)->bc.child_key;
  417.    for ( ; ch != NO_KEY; ch = l->sibling_key) {
  418.       l = db_retrieve_limb(ch);
  419.  
  420.       if (ch != our_move) {
  421.          db_delete_subtree(curnt_top_limb, ch);
  422.       }
  423.    }
  424.  
  425.    free_limb(curnt_top_limb);
  426.  
  427.    curnt_top_limb = our_move;
  428.  
  429.    tree_depth--;
  430. }
  431.